package com.mango.leet.code.spring.personal;

/**
 * 3. 二叉搜索树染色
 * @Author: mango
 * @Date: 2022/4/16 4:56 下午
 */

import java.util.Arrays;
import java.util.HashSet;
import java.util.Queue;
import java.util.Set;

/**
 * 欢迎各位勇者来到力扣城，本次试炼主题为「二叉搜索树染色」。
 *
 * 每位勇士面前设有一个二叉搜索树的模型，模型的根节点为 root，树上的各个节点值均不重复。初始时，所有节点均为蓝色。现在按顺序对这棵二叉树进行若干次操作， ops[i] = [type, x, y] 表示第 i 次操作为：
 *
 * type 等于 0 时，将节点值范围在 [x, y] 的节点均染蓝
 * type 等于 1 时，将节点值范围在 [x, y] 的节点均染红
 * 请返回完成所有染色后，该二叉树中红色节点的数量。
 *
 * 注意：
 *
 * 题目保证对于每个操作的 x、y 值定出现在二叉搜索树节点中
 * 示例 1：
 *
 * 输入：root = [1,null,2,null,3,null,4,null,5], ops = [[1,2,4],[1,1,3],[0,3,5]]
 *
 * 输出：2
 *
 * 解释：
 * 第 0 次操作，将值为 2、3、4 的节点染红；
 * 第 1 次操作，将值为 1、2、3 的节点染红；
 * 第 2 次操作，将值为 3、4、5 的节点染蓝；
 * 因此，最终值为 1、2 的节点为红色节点，返回数量 2
 * image.png
 *
 * 示例 2：
 *
 * 输入：root = [4,2,7,1,null,5,null,null,null,null,6]
 * ops = [[0,2,2],[1,1,5],[0,4,5],[1,5,7]]
 *
 * 输出：5
 *
 * 解释：
 * 第 0 次操作，将值为 2 的节点染蓝；
 * 第 1 次操作，将值为 1、2、4、5 的节点染红；
 * 第 2 次操作，将值为 4、5 的节点染蓝；
 * 第 3 次操作，将值为 5、6、7 的节点染红；
 * 因此，最终值为 1、2、5、6、7 的节点为红色节点，返回数量 5
 * image.png
 *
 * 提示：
 *
 * 1 <= 二叉树节点数量 <= 10^5
 * 1 <= ops.length <= 10^5
 * ops[i].length == 3
 * ops[i][0] 仅为 0 or 1
 * 0 <= ops[i][1] <= ops[i][2] <= 10^9
 * 0 <= 节点值 <= 10^9
 */
public class T3 {
    /**
     * Definition for a binary tree node.
     */ public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
      }

    static class Solution {
        public int getNumber(TreeNode root, int[][] ops) {
            // 定义set，只记录染红的节点的值
            Set<Integer> result = new HashSet<>();
            // ops化简
            ops = handle(ops);


            // 开始染色
            for(int[] op : ops){
                process(root,op,result);
            }
            return result.size();
        }

        private int[][] handle(int[][] ops) {
            int[] red = {1,0,0};
            int[] blue = {0,0,0};
            int flag = 0;
            for(int[] op : ops){
                if(op[0] == 0){
                    blue[1] = Math.min(blue[1],op[1]);
                    blue[2] = Math.max(blue[2],op[2]);
                }else{
                    red[1] = Math.min(red[1],op[1]);
                    red[2] = Math.max(red[2],op[2]);
                }
                flag = op[0];
            }
            System.out.println(Arrays.toString(red));
            System.out.println(Arrays.toString(blue));
            if(flag == 0){
                return new int[][]{red,blue};
            }else{
                return new int[][]{blue,red};
            }
        }

        // 遍历
        private void process(TreeNode node, int[] op, Set<Integer> result) {
            if(node == null){
                return ;
            }
            // 在 x 到 y 范围内
            if(op[1]<= node.val && node.val <= op[2]){
                if(op[0] == 0){
                    result.remove(node.val);
                }else{
                    result.add(node.val);
                }
            }
            if(node.val>op[1]) {
                process(node.left, op, result);
            }
            if(node.val<op[2]){
                process(node.right,op,result);
            }
        }
    }
}
